package Hot100.Medium.BinaryTree;

import Hot100.Easy.LC94.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class LC94_TraversalByIteration {
    public static void main(String[] args) {

    }

    public List<Integer> inOrderTraversal(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;

        TreeNode curNode = root;
        while(curNode != null || !stack.isEmpty()){
            if(curNode != null){
                stack.push(curNode);
                curNode = curNode.left;
            } else {
                curNode = stack.pop();
                res.add(curNode.val);
                curNode = curNode.right;
            }
        }
        return res;
    }
}
